package LimitedTimeGame.Day_0209;

/**
 * @author zxc
 * @date 2023/02/09 10:39
 **/

import java.util.Stack;

/**
 * 题目 ：二进制链表转换为整数
 * 题目详述 ：
 * 给你一个单链表的引用结点head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。
 * 请你返回该链表所表示数字的 十进制值 。
 *
 * 提示：
 * 链表不为空。
 * 链表的结点总数不超过 30。
 * 每个结点的值不是 0 就是 1。
 */
public class GetDecimalValue {
    /**
     * 思路 ：
     *
     * @param head
     * @return
     */
    public int getDecimalValue(ListNode head) {
        // 1.使用栈来实现
//        Stack<Integer> stack = new Stack<>();
//        while(head != null){
//            stack.push(head.val);
//            head = head.next;
//        }
//        int sum = 0;
//        int count = 0;
//        while(!stack.isEmpty()){
//            int t = stack.pop();
//            if(t == 1){
//                sum += Math.pow(2 , count);
//            }
//            count++;
//        }
//        return sum;

        // 2.首先，遍历链表，获取链表长度，然后再次遍历链表，对于其中的值进行累加;
//        int len = -1;
//        ListNode node = head;
//        while (node != null){
//            len++;
//            node = node.next;
//        }
//        int sum = 0;
//        while(head != null){
//            if (head.val == 1){
//                sum += Math.pow(2 , len);
//            }
//            len--;
//            head = head.next;
//        }
//        return sum;

        // 3.对于第二种算法优化，即不需要知道链表长度，只需要对于链表遍历一次即可
        //（1）每读取链表的一个节点值，可以认为读到的节点值是当前二进制数的最低位；
        //（2）当读到下一个节点值的时候，需要将已经读到的结果乘以 2，再将新读到的节点值当作当前二进制数的最低位；
        //（3）如此进行下去，直到读到了链表的末尾。
        int sum = 0;
        while(head != null){
            // 即，无论是否head.val为 0/1,由于对于链表进行向下遍历，使得新节点称为当前二进制数的最低位，
            // ===> 所以需要将之前的sum值进行乘2 + 当前节点值head.val;
            sum = sum * 2 + head.val;
            head = head.next;
        }
        return sum;
    }
    public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
